package structure.recursion;

import java.util.HashMap;
import java.util.Map;

public class FibonacciSequence {

    private static Map fsMap = new HashMap();
    public static long fibonacci(long k){
        if(fsMap.get(k)!=null){
            return (Long)fsMap.get(k);
        }
        if(k==0||k==1){
            fsMap.put(k,k);
            return k;
        }else{
            long value = fibonacci(k-1)+fibonacci(k-2);
            fsMap.put(k,value);
            return value;
        }
    }

    public static void main(String[] args){
        for(int i=0;i<50;i++){
            System.out.println("斐波那契数列size["+i+"],value:"+fibonacci(i));
        }
    }
}
